The present invention relates to a method and apparatus for converting a multi-level digitized image to a bi-level image.
Multi-level digitized images are generated by, for example, digital cameras, scanners, and computer software. In a multi-level monochrome image, each picture element or pixel can take on various levels of gray, the number of levels being greater than two. A multi-level color image comprises a plurality of color planes, each pixel having more than two possible levels in each color plane.
Multi-level images are often printed or displayed by bi-level output devices capable of expressing only two levels, normally a black level and a white level in a monochrome output device, or an on-level and an off-level for each color plane in a color output device. Before being output by such a device, a multi-level image must be converted to bi-level form.
Among the known techniques for converting multi-level images to bi-level images are halftone patterns, dithering, error diffusion, and mean error minimization. These terms are sometimes used with overlapping meanings; for example, mean error minimization is often referred to as error diffusion.
A halftone pattern is an m.times.m pattern of bi-level output pixels, generated from a single input pixel by using different threshold values for different pixels in the output pattern (m is an integer greater than one). Halftone patterns are often used on input images with relatively low information content, such as television images.
Dithering tiles an input image with an n.times.n matrix of differing threshold values, where n is an integer greater than one, and converts each input pixel to a single bi-level output pixel by comparing the input pixel value with the corresponding threshold value. Dithering is used in high-resolution image processing equipment, including copiers.
A problem with halftone patterns and dithering is the limited number of gray levels that can be expressed (m.sup.2 +1, or n.sup.2 +1). With small values of m and n, the limited gray scale produces unwanted contour lines in what should be smooth areas. If the value of m or n is increased to provide more gray levels, spatial resolution is lost, and the converted image begins to have a visibly blocky appearance. For this reason, dithering is rarely practiced with values of n larger than four.
The error diffusion and mean error minimization methods smooth out the errors caused by bi-level quantization. In error diffusion, the quantization error of a pixel is distributed over a certain number of subsequently-processed pixels. In the mean error minimization method, the value of a pixel is modified according to a weighted average of the quantization errors in a certain number of preceding pixels. Both methods give the same result, and can achieve comparatively smooth gray-scale expression with comparatively little loss of spatial resolution.
The error diffusion method and mean error minimization methods, however, require much computation to distribute the quantization error of each pixel individually. Processing is particularly slowed by the frequent need to access a memory area in which the quantization error values are stored.
Error diffusion or mean error minimization can also be used when a multi-level image is converted to a multi-level image with a smaller number of levels, a process sometimes referred to as color reduction. Compared with bi-level error diffusion, multi-level error diffusion yields a considerable improvement in image quality, even if the number of output levels is only three, but requires a multi-level output device, which is more expensive than a bi-level output device.